package com.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * 677. 键值映射
 * 使用 固定26个值的数组的26叉树
 * 借助map, 在node中存的值就是prefix的前缀值
 *
 * @author fy
 * @date 2022/4/19 14:44
 */
public class Solution677_2 {

    static class MapSum {
        class TrieNode {
            int val = 0;
            TrieNode[] next = new TrieNode[26];
        }

        TrieNode root;
        Map<String, Integer> map;

        public MapSum() {
            root = new TrieNode();
            map = new HashMap<>();
        }

        public void insert(String key, int val) {
            int delta = val - map.getOrDefault(key, 0);
            map.put(key, val);
            TrieNode node = root;
            for (char c : key.toCharArray()) {
                if (node.next[c - 'a'] == null) {
                    node.next[c - 'a'] = new TrieNode();
                }
                node = node.next[c - 'a'];
                node.val += delta;
            }
        }

        public int sum(String prefix) {
            TrieNode node = root;
            for (char c : prefix.toCharArray()) {
                if (node.next[c - 'a'] == null) {
                    return 0;
                }
                node = node.next[c - 'a'];
            }
            return node.val;
        }
    }

    public static void main(String[] args) {
        MapSum ms = new MapSum();
        ms.insert("apple", 3);
        System.out.println(ms.sum("ap"));
        ms.insert("app", 2);
        System.out.println(ms.sum("ap"));
    }

}
